﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * 
The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

     * */
    class Problem87 : IProblem
    {
        public string Calculate()
        {
            List<long> squares = new List<long>() { 4 };
            List<long> cubes = new List<long>() { 8 };
            List<long> fourths = new List<long>() { 16 };

            SieveOfAtkin sieve = new SieveOfAtkin(10000);

            long limit = 50000000;


            bool cubeOverflow = false;
            bool fourthOverflow = false;

            for (int i = 1; i < 10000; i+=2)
            {
                if (sieve.IsPrime(i))
                {
                    long square = i * i;
                    if (square < limit)
                    {
                        squares.Add(square);

                        if (!cubeOverflow)
                        {
                            long cube = i * i * i;
                            if (cube < limit)
                            {
                                cubes.Add(cube);
                                if (!fourthOverflow)
                                {
                                    long fourth = i * i * i * i;
                                    if (fourth < limit)
                                        fourths.Add(fourth);
                                    else
                                        fourthOverflow = true;
                                }
                            }
                            else
                            {
                                cubeOverflow = true;
                            }
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }

            long count = 0;

            List<long> sums = new List<long>();

            for (int i = 0; i < squares.Count; i++)
            {
                if (squares[i] + cubes[0] + fourths[0] >= limit)
                    break;

                for (int j = 0; j < cubes.Count; j++)
                {
                    if (squares[i] + cubes[j] + fourths[0] >= limit)
                        break;

                    for (int k = 0; k < fourths.Count; k++)
                    {
                        long sum = squares[i] + cubes[j] + fourths[k];
                        if (sum >= limit)
                            break;
                        count++;
                        sums.Add(sum);
                    }
                }
            }


            return sums.Distinct().Count().ToString();
        }
    }
}
